// 栈
// "消消乐" 问题，要想到使用栈的思想解决
// 表达式求值问题 - 使用栈模拟计算过程，栈是一种思想，不局限于形式（可以是 stringBuilder， 也可以是 数组）

// 例题 3：
// 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
//
//        整数除法仅保留整数部分。
//
//        你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
//
//        注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
//
//        示例 1：
//
//        输入：s = "3+2*2"
//        输出：7
//        示例 2：
//
//        输入：s = " 3/2 "
//        输出：1
//        示例 3：
//
//        输入：s = " 3+5 / 2 "
//        输出：5

// 解题思路：
// 字符串表达式求值的问题，要使用栈去模拟计算过程
// 因为表达式中只有 “+”，“-”，“*”，“/” ，因此可以使用一个栈存放数字，一个变量存放运算符号
// 初始化的时候给存放符号的变量初始化成 “+”
// 分情况讨论：
//      如果是数字 - 提取数字；
//      如果是符号 - 更新符号变量
//      如果是空格 - 跳过去
// 每提取一个数字，都要结合前面的符号运算，结果存放到栈中
// 最终结果就是栈中所有元素的和

import java.util.Stack;

public class Calculate {
    // 解法 1：一个栈 + 符号变量
    public int calculate1(String s) {
        int n = s.length();
        char[] sArr = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        char op = '+';
        int i = 0;
        while(i < n){
            if(sArr[i] >= '0' && sArr[i] <= '9'){
                int tmp = 0;
                while(i < n && sArr[i] >= '0' && sArr[i] <= '9'){
                    tmp *= 10;
                    tmp += sArr[i] - '0';
                    i++;
                }
                if(op == '+') stack.push(tmp);
                else if(op == '-') stack.push(-tmp);
                else if(op == '*') {
                    int num = stack.pop();
                    stack.push(num * tmp);
                }else{
                    int num = stack.pop();
                    stack.push(num / tmp);
                }
            }else if(sArr[i] == ' ') i++;
            else{
                op = sArr[i];
                i++;
            }
        }
        int ret = 0;
        while(!stack.isEmpty()) ret += stack.pop();
        return ret;
    }
    // 解法 2：使用 数组 和一个 下标变量 模拟栈
    public int calculate2(String s) {
        int n = s.length();
        char[] sArr = s.toCharArray();
        int[] nums = new int[n];
        int pos = 0;
        char op = '+';
        int i = 0;
        while(i < n){
            if(sArr[i] == ' ') i++;
            else if(sArr[i] >= '0' && sArr[i] <= '9'){
                int tmp = 0;
                while(i < n && sArr[i] >= '0' && sArr[i] <= '9'){
                    tmp *= 10;
                    tmp += sArr[i] - '0';
                    i++;
                }
                if(op == '+') nums[pos++] = tmp;
                else if(op == '-') nums[pos++] = -tmp;
                else if(op == '*') nums[pos - 1] *= tmp;
                else nums[pos - 1] /= tmp;
            }else {
                op = sArr[i];
                i++;
            }
        }
        int ret = 0;
        for(int num : nums) ret += num;
        return ret;
    }
    // 解法 3：使用双栈分别模拟数字和符号
    public int calculate3(String s) {
        int n = s.length();
        char[] sArr = s.toCharArray();
        Stack<Integer> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        stack2.push('+');
        int i = 0;
        while(i < n){
            if(sArr[i] >= '0' && sArr[i] <= '9'){
                int tmp = 0;
                while(i < n && sArr[i] >= '0' && sArr[i] <= '9'){
                    tmp *= 10;
                    tmp += sArr[i] - '0';
                    i++;
                }
                if(stack2.peek() == '*') {
                    int num = stack1.pop();
                    stack1.push(num * tmp);
                    stack2.pop();
                }else if(stack2.peek() == '/'){
                    int num = stack1.pop();
                    stack1.push(num / tmp);
                    stack2.pop();
                }else if(stack2.peek() == '+') {
                    stack1.push(tmp);
                    stack2.pop();
                }else{
                    stack1.push(-tmp);
                    stack2.pop();
                }
            }else if(sArr[i] == ' ') i++;
            else {
                stack2.push(sArr[i]);
                i++;
            }
        }
        int ret = 0;
        while(!stack1.isEmpty()) ret += stack1.pop();
        return ret;
    }
}
